package day08;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/4/8 15:24
 */

/**
 * 「力扣嘉年华」的中心广场放置了一个巨型的二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1 表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：
 *
 * 开关 1：切换当前节点的灯的状态；
 * 开关 2：切换 以当前节点为根 的子树中，所有节点上的灯的状态，；
 * 开关 3：切换 当前节点及其左右子节点（若存在的话） 上的灯的状态；
 * 给定该装饰的初始状态 root，请返回最少需要操作多少次开关，可以关闭所有节点的灯。
 *
 * 示例 1：
 *
 * 输入：root = [1,1,0,null,null,null,1]
 *
 * 输出：2
 *
 * 解释：以下是最佳的方案之一，如图所示b71b95bf405e3b223e00b2820a062ba4.gif
 *
 * 示例 2：
 *
 * 输入：root = [1,1,1,1,null,null,1]
 *
 * 输出：1
 *
 * 解释：以下是最佳的方案，如图所示a4091b6448a0089b4d9e8f0390ff9ac6.gif
 *
 * 示例 3：
 *
 * 输入：root = [0,null,0]
 *
 * 输出：0
 *
 * 解释：无需操作开关，当前所有节点上的灯均已关闭
 */
class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
     TreeNode(int x) { val = x; }
}
public class Solution5 {
    public int closeLampInTree(TreeNode root) {
        return DpTree(root)[0];
    }
    public int[] DpTree(TreeNode root){
        if(root==null){
            return new int[]{0,0,0,0};
        }
        int []dp = new int[4];
        int on = root.val ,off = root.val==1?0:1;
        int []l = DpTree(root.left),r = DpTree(root.right);
        dp[0]=fmin(l[0]+r[0]+on,l[1]+r[1]+off+1,l[2]+r[2]+off+1,l[3]+r[3]+on+2);
        dp[1]=fmin(l[0]+r[0]+on+1,l[1]+r[1]+off,l[2]+r[2]+off+2,l[3]+r[3]+on+1);
        dp[2]=fmin(l[0]+r[0]+off,l[1]+r[1]+on+1,l[2]+r[2]+on+1,l[3]+r[3]+off+2);
        dp[3]=fmin(l[0]+r[0]+off+1,l[1]+r[1]+on,l[2]+r[2]+on+2,l[3]+r[3]+off+1);
        return dp;
    }
    public int fmin(int a,int b, int c,int d){
        return Math.min(Math.min(Math.min(a,b),c),d);
    }
}
